package com.cqs.leetcode.sort;

import com.cqs.leetcode.TestCaseUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author lixiaowen
 * @create 2020-01-01
 */
public class SortColors75 {


    static class Solution {
        public void sortColors(int[] nums) {
            //三指针p0 0的右边界  p2 2的左边界
            int p0 = -1, p2 = nums.length, cur = -1;
            while (++cur < nums.length && cur < p2) {
                switch (nums[cur]) {
                    case 0:
                        swap(nums, ++p0, cur);
                        break;
                    case 2:
                        swap(nums, --p2, cur);
                        if (nums[cur] != 1) {
                            --cur;
                        }
                        break;
                    default:
                        break;
                }
            }
        }

        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

    static class Solution2 {
        public void sortColors(int[] nums) {
            int left = 0, right = nums.length - 1, rightOne = -1;
            while (left < right) {
                while (left < right && nums[left] == 0) ++left;
                while (left < right && nums[right] != 0) --right;
                if (left < right) {
                    swap(nums, left, right);
                }
            }
            left = right;
            right = nums.length - 1;
            while (left < right) {
                while (left < right && nums[left] == 1) ++left;
                while (left < right && nums[right] != 1) --right;
                if (left < right) {
                    swap(nums, left, right);
                }
            }
        }

        private void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < 0; i++) {
            list.add(random(10));
        }
        //list.add(new int[]{1, 1, 0, 1, 2, 0, 0, 2, 1, 0});
        list.add(new int[]{2, 0, 2, 1, 1, 0});

        list.stream().forEach(it -> {
            String str = TestCaseUtils.arrFormat(it);
            solution.sortColors(it);

            System.out.println(str + "\r\n" + TestCaseUtils.arrFormat(it));
            System.out.println("======================\n");
        });
    }

    private static int[] random(int m) {
        int[] list = new int[m];
        for (int i = 0; i < m; i++) {
            list[i] = new Random().nextInt(3);
        }
        return list;
    }
}
